package com.ma.problem;

public class dutchFlag {
    public static void run(int[] arr){

    }

    /**
     * 荷兰国旗问题解决
     * @param arr
     * @param L
     * @param R
     * @return
     */
    /*
        将小于arr[R]划分在左、等于arr[R]在中间、大于arr[R]划分在右
        通过逐步扩大>区和<区的方式实现
        保留arr[R]位置不动
        如果=arr[R]时i向右移动
        如果<arr[R]时把<区下一位置的数与i交换再i向右移动
        如果>arr[R]时把>区上一位置的数与i交换再i向左移动
        最后再将保留的arr[R]与>区的第一个交换
        那么最后交换的位置即(交换前more位置)与<区+1位置就是=区位置
     */
    public static int[] netherlandsFlag(int[] arr,int L,int R){
        if(L>R){
            return new int[]{-1,-1};
        }
        if(L==R){
            return new int[]{L,R};
        }
        int less=L-1;
        int more=R;
        int i=L;
        while (i<more){
            if(arr[i]==arr[R]){
                i++;
            }else if(arr[i]<arr[R]){
                swap(arr,i++,++less);
            }else {
                swap(arr,i,--more);
            }
        }
        swap(arr,more,R);
        return new int[]{L+1,more};
    }

    private static void swap(int[] arr, int less, int more) {
        arr[less]=arr[less]^arr[more];
        arr[more]=arr[less]^arr[more];
        arr[less]=arr[less]^arr[more];
    }


}
